package com.jack.leetcode.eachproblem_2020;

/**
 * Created by zhang_j on 2020/10/23
 */
public class 前缀树 {

    class TrieNode{
        private TrieNode[] links;
        private static final int R = 26;
        private boolean isEnd;
        TrieNode(){
            links = new TrieNode[R];
        }
        public boolean containsKey(char c){
            return links[c - 'a'] != null;
        }
        public TrieNode get(char c){
            return links[c - 'a'];
        }
        public void put(char c, TrieNode node){
            links[c - 'a'] = node;
        }
        public void setEnd(){
            isEnd = true;
        }
        public boolean isEnd(){
            return isEnd;
        }
    }

    class Trie {
        private TrieNode[] tries = new TrieNode[26];
        private TrieNode root;
        /** Initialize your data structure here. */
        public Trie() {
            root = new TrieNode();
        }

        /** Inserts a word into the trie. */
        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if(!node.containsKey(c)){
                    node.put(c, new TrieNode());
                }
                node = node.get(c);
            }
            node.setEnd();
        }

        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            TrieNode node = root;
            for(char c : word.toCharArray()){
                if(node == null){
                    return false;
                }
                node = node.get(c);
            }
            return node.isEnd();
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            TrieNode node = root;
            for(char c : prefix.toCharArray()){
                if(node.get(c) == null){
                    return false;
                }
                node = node.get(c);
            }
            return true;
        }
    }
}
